This application relates to a compiler and, specifically, to an LALR syntactical analyzer and semantic checker in a compiler for a high level computer programming language.
Conventionally, a high level computer programming language is described by a "grammar" for the language. A grammar is formed by a series of "productions." Each production has a left hand side (LHS), representing statement or construct in the language; a symbol (such as ".fwdarw."); and a right hand side (RHS), representing a series of other statements or constructs that make up the LHS statement. For example, a first production in a grammar for the pascal programming language might be:
This production indicates that a pascal program consists of three parts: a program header, declarations of variables and constants, and a block that includes the actions performed by the program. A pascal program of the example is ended by a period (".").
A further production in the grammar might be:
Thus, a program header consists of three parts: the word "prog", an identifier, and a list of zero or more file identifiers followed by a semicolon.
A compiler is a computer program that translates a "source program" written in a high level computer programming language that is easily understood by human beings into a "target program" executable by a computer. Typically, a compiler includes several functional parts. For example, a conventional compiler may include a lexical analyzer that looks at the source program and identifies successive "tokens" in the source program.
A conventional compiler also includes a parser/syntactical analyzer, which takes as an input a grammar defining the language being compiled and a series of actions associated with respective production of the grammar. The syntactical analyzer builds a "parse tree" for the statements in the source program in accordance with the grammar productions and actions. For each statement in the input source program, the syntactical analyzer generates a parse tree of the source input in a recursive, "bottom-up" manner in accordance with relevant productions and actions in the grammar. Thus, the parse tree is formed of nodes corresponding to one or more grammar productions. Generation of the parse tree allows the syntactical analyzer to determine whether the parts of the source program comply with the grammar. If not, the syntactical analyzer generates an error. Thus, the syntactical analyzer performs syntactical checking, but does not conventionally check the meaning (the "semantics") of the source program. One example of a conventional parsing technique is a LALR (lookahead, left right) syntactical analyzer, which is described in Chapter 4 of the treatise "Compilers: Principles, Techniques and Tools" by Aho, Sethi, and Ullman, the entirety of which is hereby incorporated by reference.
In conventional compilers, after the source program is parsed, it is input to a semantic analyzer, which checks for semantic errors, such as the mismatching of types, etc. The semantic analyzer evaluates, for example, "semantic attributes" of nodes of the parse tree. Attributes that are evaluated by looking at the attributes of their child nodes are called "synthesized attributes." After parsing and semantic analysis, the compiler generates intermediate code, optimizes the intermediate code and generates a target program.
It is important that compilers execute quickly and efficiently. In conventional compilers, the design of the semantic analyzer leads to inefficiencies of operation. Specifically, in conventional compilers, semantic attributes are evaluated in a separate parse tree-traversals during semantic analysis of the parse tree, after the parse tree has been completely constructed. Use of a separate tree-traversal for each semantic attribute causes an exponential increase in the amount of time required for compilation. Use of a separate pass for each semantic attribute requires the compiler to do a recursive descent through the parse tree for each attribute and an additional descent through the parse tree to do full semantic analysis and code generation. What is needed is a way to increase the efficiency of semantic analysis in a compiler so the execution time of the compiler is decreased.